import java.util.*;
// 牛客网 kotori和气球
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        if(m > n) {
            System.out.print(0);
            return;
        }
        if(m == 1) {
            System.out.print(m);
            return;
        }
        if(n == 1) {
            System.out.print(1);
            return;
        }
        int res = n;
        for(int i = 1; i < m; i++) {
            res = res * (n-1) % 109;
        }
        System.out.print(res);
    }
}




// 牛客网 AB20 走迷宫
class Solution {
    // 定义上下左右四个方向（行、列偏移量）
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();

        // 读取起点（x1,y1）和终点（x2,y2），已转换为 0 索引
        int[] start = new int[2];
        int[] target = new int[2];
        start[0] = in.nextInt() - 1;
        start[1] = in.nextInt() - 1;
        target[0] = in.nextInt() - 1;
        target[1] = in.nextInt() - 1;

        // 读取网格
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = in.next().toCharArray();
        }

        // 边界判断：终点是障碍物，直接输出 -1
        if (grid[target[0]][target[1]] == '*') {
            System.out.print(-1);
            return;
        }

        // 初始化：dist 数组既存距离，也做访问标记（-1 表示未访问）
        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dist[i][j] = -1;
            }
        }

        // BFS 队列：存储格子的（行，列）
        Queue<int[]> queue = new LinkedList<>();
        // 起点入队：距离设为 0，标记为已访问
        queue.offer(start);
        dist[start[0]][start[1]] = 0;

        // 执行 BFS
        while (!queue.isEmpty()) {
            // 取出队首格子（当前层次的格子）
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];

            // 终止条件：到达终点，直接输出距离（BFS 首次到达即最短）
            if (x == target[0] && y == target[1]) {
                System.out.print(dist[x][y]);
                return;
            }

            // 遍历四个方向
            for (int[] dir : DIRS) {
                int nx = x + dir[0]; // 新行
                int ny = y + dir[1]; // 新列

                // 新格子需满足：1. 在网格内 2. 不是障碍物 3. 未访问过
                if (nx >= 0 && nx < n && ny >= 0 && ny < m
                        && grid[nx][ny] != '*' && dist[nx][ny] == -1) {
                    // 更新距离（当前距离 + 1）
                    dist[nx][ny] = dist[x][y] + 1;
                    // 新格子入队，等待下一层遍历
                    queue.offer(new int[] {nx, ny});
                }
            }
        }

        // 队列空了仍未到达终点：无路径，输出 -1
        System.out.print(-1);
    }
}